/**
 * @defgroup Algorithm.java TODO
 * @author 李焕帅
 * @version TODO
 * @date TODO
 * @{
 */
/**
 * @name 包定义
 * @{
 */
package indd.lihs.basic.utils;

/** @}*/
// 包定义

/**
 * @name 类型定义
 * @{
 */
/**
 * @name TODO
 * @{
 */
public class Algorithm
{

    /**
     * TODO
     * @parm [in] TODO TODO
     * @return void
     * @note TODO
     * @par TODO
     * @code
     * TODO
     * @endcode
     * @see TODO
     */
    public static void main(String[] args)
    {
        Integer[] a = {4, 2, 1, 3, 6, 1};
        Algorithm.QuickSort(a, 0, a.length-1);
        for (Integer i : a) System.out.println(i);
    }
    
    /**
     * TODO
     * @parm [in] TODO TODO
     * @return void
     * @note TODO
     * @par TODO
     * @code
     * TODO
     * @endcode
     * @see TODO
     */
    public static <T extends Comparable<T>> void QuickSort(T[] a, int s, int t)
    {//排序a[s:t]
    	if (s >= t) return;
    	
        int i = s;  //左向右的游标
        int j = t+1; //右向左的游标
        T pivot = a[s]; //使用当前第一个元素作为轴
                
        // 双扫描
        while (true)
        {
            do
            {
                ++i;
            } while (i < a.length && 0 < a[i].compareTo(pivot));
            do
            {
                --j;
            } while (j > 0 && 0 > a[j].compareTo(pivot));
            if (i >= j) break;
            Swap(a, i, j);
        }
        
        a[s] = a[j];
        a[j]= pivot;
        
        QuickSort(a, s, j-1);
        QuickSort(a, j+1, t);
    }
    
    public static <T> void Swap(T[] a, int i, int j)
    {
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

/** @}*/	// 类型定义
/** @}*/	// 模块定义